Адміністрація вирішила продати даний сайт. За детальною інформацією звертайтесь за адресою: rozrahu@gmail.com

Застосування генетичних алгоритмів для вирішення задачі комівояжера.

Інформація про навчальний заклад

ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Електронні обчислювальні машини

Інформація про роботу

Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Дослідження комп'ютерних систем штучного інтелекту
Група:
КСМм-1

Частина тексту файла

Міністерство освіти і науки України Національний університет „Львівська політехніка” Кафедра електронних обчислювальних машин Звіт про виконання лабораторної роботи №3(4) з курсу „ Дослідження комп'ютерних систем штучного інтелекту ” Тема: Застосування генетичних алгоритмів для вирішення задачі комівояжера Виконав: ст. гр. КСМм-1 Львів – 2007 Мета: ознайомитись з методами вирішення задач за допомогою генетичних алгоритмів та використати даний алгоритм для вирішення задачі комівояжера. Теоретичні відомості Задача комівояжера у стандартній постановці виглядає так: є набір міст, потрібно відвідати найкоротшим шляхом всі міста, але кожне місто відвідується лише раз і повернутись до відправного пункту. Формально TSP можна вирішити наступним чином: Даними є: натуральні числа n ≥ 3 i маршрут C =(cij), де cij - ітераційний підрахунок, що циклічно змінюється. EMBED Equation.3 TSP є відносно старою проблемою. Вперше вона була сформульована Ейлером в 1759 році (але під іншою назвою), якій хотів розв”язати проблему шахового коня. Правильне розв”язання повинно містити шлях шахового коня по всіх 64 шахових клітинах, так щоб на кожній клітині поля кінь побував лише один раз. Термін ‘travelling salesman’ вперше був застосований в 1932 році у німецькій книзі, присвяченій вирішенню задачі комівояжера. Після багатьох років, проблема комівояжера дочекалась на багато способів розв”язання. Існує декілька причин цього. По перше TSP є дуже простим в описуванні, але важким у розв’язанні. Не знаємо жодного алгоритму, що розв’язує це завдання миттєво в баготовимірному часі. Цей недолік алгоритму, що розв’язує завдання багатовимірному часі є характерним для проблем, відомих під назвою NP – повних, для яких проблема комівояжера є класичним прикладом. По друге, TSP має застосування в багатьох різних проблемах, що зачіпають різного роду шляхи і пункти. По трете, по мірі отримання багато інформації на тему проблеми комівояжера, згодом її можна використовувати як свого роду тестову задачу, нові комбанаторні методи часто тестуються на TSP, з метою переконання в їх приктичній здатності. І зрештою велика кількість проблем, в яких маємо відповідно до завдань штучного інтелекту, призводять до знаходження найкращої permutacji n елементів. Представлення і оператори Відомо багато різних способів представлення здатних до розв”язування проблеми комівояжера за допомогою генетичних алгоритмів. Деякі з них як бінарі рішення чи маршрутне рішення використовують бінарні значення для представлення даного шляху. Хоча таке рішення є стандартом в світі генетичних алгоритмів, однак для задачі комівояжера проблемою є те, що оператори схрещуваня і мутації можуть давати погані наслідки. Для того мусимо залишити сформульовані оператори виправлень. Найкращим природнім способом представлення шляху є вигляд представлення. В цьому представленні n міст, які мають розмістити пункти відвідувань в n-елементний ланцюжок таким чином, що якщо і-те місто знаходиться в j-ій позиції за рахунком, це означає, що і-те місто відвідане як j-те. Таке представлення дозволяє сформулювати велику кількість різних операторів схрещування і мутації. Можна стверджувати, що на даний час більшість генетичних алгоритмів, що заходять приблизне розв”язання задачі комівояжера вживають таке представлення. Вагомою причиною для того є інтуїтивна простота і природність представлення, а також добрі наслідки, отримані при його застосуванні Бінарне представлення В бінарному представленні задачі комівояжера для n-міст, кожне місто закодовано у ланцюжок довжиною [log2 n] бітів. Одиночне рішення зрештою є ланцюжком, довжиною n*[log2 n] бітів. Наприклад, при шістьох містах кожне місто представлено ланцюжком довжиною у 3 біти Шлях 1-2-3-4-5-6 представлятиметься: 000 001 010 011 100 101 Зауважимо, що існують 3-бітові ланцюжки. З них не кодують жодного міста: 110 і 111 Класичне схрещування (Classical Crossover) Оператор класичного схрещування був запропонований Голандом (1975). ...
Антиботан аватар за замовчуванням

01.01.1970 03:01

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, увійдіть або зареєструйтесь.

Завантаження файлу

Якщо Ви маєте на своєму комп'ютері файли, пов'язані з навчанням( розрахункові, лабораторні, практичні, контрольні роботи та інше...), і Вам не шкода ними поділитись - то скористайтесь формою для завантаження файлу, попередньо заархівувавши все в архів .rar або .zip розміром до 100мб, і до нього невдовзі отримають доступ студенти всієї України! Ви отримаєте грошову винагороду в кінці місяця, якщо станете одним з трьох переможців!
Стань активним учасником руху antibotan!
Поділись актуальною інформацією,
і отримай привілеї у користуванні архівом! Детальніше

Оголошення від адміністратора

Антиботан аватар за замовчуванням

пропонує роботу

Admin

26.02.2019 12:38

Привіт усім учасникам нашого порталу! Хороші новини - з‘явилась можливість кожному заробити на своїх знаннях та вміннях. Тепер Ви можете продавати свої роботи на сайті заробляючи кошти, рейтинг і довіру користувачів. Потрібно завантажити роботу, вказати ціну і додати один інформативний скріншот з деякими частинами виконаних завдань. Навіть одна якісна і всім необхідна робота може продатися сотні разів. «Головою заробляти» продуктивніше ніж руками! :-)

Новини